package com.lili.sort;

import java.util.*;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 桶排序优化
 * @version: 1.0
 */
public class BucketSort2 {
    /*
     * 概要: 将数据分组放入桶里面进行排序(以人类年龄为例子 1-99)
     */
    public static int[] bucketSort(int[] arr, int range) {
        int maxNUm = arr[0];
        int minNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNUm) {
                maxNUm = arr[i];
            }
            if (arr[i] < minNum) {
                minNum = arr[i];
            }
        }

        List<Integer>[] lists = new List[(maxNUm - minNum) / range + 1];
        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i : arr) {
            lists[(i - minNum) / range].add(i);
        }
        int k = 0;
        for (List<Integer> list : lists) {
            //桶内元素进行排序: 这个地方可以用一种方式进行排序
            Integer[] array = (Integer[]) (list.toArray());
            Arrays.sort(array);
            for (int v : array) {
                arr[k] = v;
                k++;
            }
        }
        return arr;
    }

}
